﻿// 2447. 最大公因数等于 K 的子数组数目.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <iostream>
#include <vector>



using namespace std;


/*
https://leetcode.cn/problems/number-of-subarrays-with-gcd-equal-to-k/description/

给你一个整数数组 nums 和一个整数 k ，请你统计并返回 nums 的子数组中元素的最大公因数等于 k 的子数组数目。

子数组 是数组中一个连续的非空序列。

数组的最大公因数 是能整除数组中所有元素的最大整数。



示例 1：
输入：nums = [9,3,1,2,6,3], k = 3
输出：4
解释：nums 的子数组中，以 3 作为最大公因数的子数组如下：
- [9,3,1,2,6,3]
- [9,3,1,2,6,3]
- [9,3,1,2,6,3]
- [9,3,1,2,6,3]

示例 2：
输入：nums = [4], k = 7
输出：0
解释：不存在以 7 作为最大公因数的子数组。


提示：

1 <= nums.length <= 1000
1 <= nums[i], k <= 109
*/


class Solution {
public:
    int gcd(int a, int b) {
        if (b == 0) return a;
        return gcd(b, a % b);
    }
    int subarrayGCD(vector<int>& nums, int k) {
        int ans = 0;
        for (int i = 0; i < nums.size(); i++) {
            int gcdv = nums[i];
            if (gcdv == k) ans++;
            for (int j = i + 1; j < nums.size(); j++) {
                gcdv = gcd(gcdv, nums[j]);
                if (gcdv == k) ans++;
            }
        }

        return ans;
    }
};



int main()
{


	return 0;
}

 